class Solution {
public:
    vector<TreeNode*> generateTrees(int start, int end) {
        if (start > end)
        {
            return { nullptr };
        }
        vector<TreeNode*> allTrees;
        for (int i = start; i <= end; i++) // 枚举可行根节点
        {
            vector<TreeNode*> leftTrees = generateTrees(start, i - 1); // 获得所有可行的左子树集合
            vector<TreeNode*> rightTrees = generateTrees(i + 1, end); // 获得所有可行的右子树集合
            
            for (auto& left : leftTrees)
            {   // 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上
                for (auto& right : rightTrees)
                {
                    TreeNode* currTree = new TreeNode(i);
                    currTree->left = left;
                    currTree->right = right;
                    allTrees.emplace_back(currTree);
                }
            }
        }
        return allTrees;
    }

    vector<TreeNode*> generateTrees(int n) {
        if (!n)
            return {};
        return generateTrees(1, n);
    }
};